package Interview.Amazon;

import util.SwapUtil;

/**
 * 数组有N+M个数字, 数字的范围为1 ... N, 打印重复的元素
 * 要求O(M + N), 不可以用额外的空间
 */
public class Test02打印数组中重复元素 {
    public static void main(String[] args) {
        int[] array = {5, 4, 4, 6, 9, 3, 8, 7, 1, 6, 5, 6};
        printDupNum(array);
    }

    /**
     * 遍历数组
     * 将数值为value（范围是1...N）的元素放到value - 1的位置，
     * 如果该元素就在value - 1的位置，则遍历下一个元素。
     * 如果value - 1位置的数值为value，则说明value是重复元素，打印。
     * 如果value - 1位置的数值不为value，则交换两个元素。
     * @param array
     */
    public static void printDupNum(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int i = 0;
        while (i < array.length) {
            int value = array[i];
            //如果该元素就在x-1的位置，则遍历下一个元素
            if (value == 0 || i == value - 1) {
                i++;
            } else if (array[value - 1] == value) {
                System.out.print(value);
                System.out.print(" ");
                array[i++] = 0;
            } else {
                SwapUtil.swap(array, i, value - 1);
            }
        }
    }

}
